package code.starivan.leetcode;

/**
 * Created by Ivan on 2015/10/19.
 */

/*
Suppose a sorted array is rotated at some pivot unknown to you beforehand.

        (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

        You are given a target value to search. If found in the array return its index, otherwise return -1.

        You may assume no duplicate exists in the array.
*/

public class N033_SearchinRotatedSortedArray {
    public static void test(){
        System.out.println(new N033_SearchinRotatedSortedArray().search(new int[]{4,5,6,7,0,1,2},2));
    }
    public int search(int[] nums, int target) {
        if(nums==null||nums.length==0){
            return -1;
        }

        int index=0;
        for(index=0;index<nums.length-1;++index){
            if(nums[index]>nums[index+1])
                break;
        }

        if(index==nums.length-1){
            return binarySearch(nums,0,nums.length-1,target);
        }else {
            int ret=binarySearch(nums,0,index,target);
            if(ret==-1){
                return binarySearch(nums,index+1,nums.length-1,target);
            }else{
                return ret;
            }
        }
    }

    private int binarySearch(int[] arr,int left,int right,int target){
        while (left<=right){
            int mid=(right+left)/2;
            if(arr[mid]==target){
                return mid;
            }else if(arr[mid]>target){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }

        return -1;
    }
}
